#include <bits/stdc++.h>

#define in read()
#define fi first
#define se second
#define pii pair<int,int>
#define pb push_back
#define vec vector<int>
#define y1 y_____hahahaha_____1

using namespace std;

typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;

ll read(){ll x = 0,sgn = 1;char ch = getchar();for(;!isdigit(ch);ch = getchar()) if(ch == '-') sgn = -1;for(;isdigit(ch);ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48); return x * sgn;}

const int mod = 2333;

int C[mod + 2][mod + 2];

int f(ll n,ll k){
	if(n < mod) return C[n][min(n,k)];
	if(!k) return 1;
	int ans = 0;
	ans = f(n / mod,k / mod) * C[n % mod][min(n % mod,k % mod)] % mod;
	if(k / mod) ans = (ans + f(n / mod,k / mod - 1) * (C[n % mod][min(mod - 1ll,n % mod)] - C[n % mod][min(n % mod,k % mod)] + mod) % mod) % mod;
	return ans;
}

ll n,k;

int main(){
#ifndef ONLINE_JUDGE
	freopen("1.in","r",stdin);
#endif
	C[0][0] = 1;
	for(int i = 1;i < mod;i++){
		C[i][0] = 1;
		for(int j = 1;j <= i;j++)
			C[i][j] = (C[i-1][j] + C[i-1][j-1]) % mod;
	}
	for(int i = 1;i < mod;i++)
		for(int j = 1;j <= i;j++)
			C[i][j] = (C[i][j - 1] + C[i][j]) % mod;
	for(int T = in;T;T--) n = in,k = in,printf("%d\n",f(n,k));
	return 0;
}
